// 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。
// 有效字符串具有如下规则：
//     任何左括号 ( 必须有相应的右括号 )。
//     任何右括号 ) 必须有相应的左括号 ( 。
//     左括号 ( 必须在对应的右括号之前 )。
//     * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
//     一个空字符串也被视为有效字符串。
// 示例 1:
// 输入: "()"
// 输出: True

// 示例 2:
// 输入: "(*)"
// 输出: True

// 示例 3:
// 输入: "(*))"
// 输出: True

// 注意:
//     字符串大小将在 [1，100] 范围内。
///////思路：
        // 解法1：一个正向一个反向遍历 分别把*当做左括号和有括号
        ///解法2：栈
/**
 * @param {string} s
 * @return {boolean}
 */
// var checkValidString = function(s) {
//     if(s.length === 0) return true;
//     let left = 0, right = 0, len = s.length;
//     for(let i = 0; i < len; i++) {
//         if (s[i] === '(' || s[i] === '*') {
//             left++;
//         } else {
//             left--;
//         }
//         if (s[len - i - 1] === ')' || s[len - i - 1] === '*') {
//             right++;
//         } else {
//             right--;
//         }
//         if (left < 0 || right < 0) {
//             return false;
//         }
//     }

//     return true;
// };
///////////栈是最容易想到的  一个左括号栈 一个星号栈
var checkValidString = function(s) {
    if(s.length === 0) return true;
    let leftStack = [], starStack = [];
    for(let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            leftStack.push(s[i]);
        } else if(s[i] === '*') {
            starStack.push(s[i]);
        } else {
            if (leftStack.length > 0) {
                leftStack.pop();
            } else  if (starStack.length > 0) {
                starStack.pop();
            } else {
                return false;
            }
        }
    }
    ////判断如果左括号栈不为空, 因为左括号的位置要在星号位置前才能满足条件，否则也不满足，所以不能简单的判断数量
    while(leftStack.length > 0) {
        if (starStack.length === 0) return false;
        let posL = leftStack[leftStack.length - 1];
        let posS = starStack[starStack.length - 1];
        if (posL < posS) {
            leftStack.pop();
            starStack.pop();
        } else {
            return false;
        }
    }
    return true;
};

console.log(checkValidString("(*))"))

